//有一条无限长的数轴，原点在 0 处，沿着 x 轴 正 方向无限延伸。 
//
// 给你一个二维数组 queries ，它包含两种操作： 
//
// 
// 操作类型 1 ：queries[i] = [1, x] 。在距离原点 x 处建一个障碍物。数据保证当操作执行的时候，位置 x 处 没有 任何障碍物。 
// 操作类型 2 ：queries[i] = [2, x, sz] 。判断在数轴范围 [0, x] 内是否可以放置一个长度为 sz 的物块，这个物块需要 完全
// 放置在范围 [0, x] 内。如果物块与任何障碍物有重合，那么这个物块 不能 被放置，但物块可以与障碍物刚好接触。注意，你只是进行查询，并 不是 真的放置这个
//物块。每个查询都是相互独立的。 
// 
//
// 请你返回一个 boolean 数组results ，如果第 i 个操作类型 2 的操作你可以放置物块，那么 results[i] 为 true ，否则为 
//false 。 
//
// 
//
// 示例 1： 
//
// 
// 输入：queries = [[1,2],[2,3,3],[2,3,1],[2,2,2]] 
// 
//
// 输出：[false,true,true] 
//
// 解释： 
//
// 
//
// 查询 0 ，在 x = 2 处放置一个障碍物。在 x = 3 之前任何大小不超过 2 的物块都可以被放置。 
//
// 示例 2： 
//
// 
// 输入：queries = [[1,7],[2,7,6],[1,2],[2,7,5],[2,7,6]]
// 
// 
//
// 输出：[true,true,false] 
//
// 解释： 
//
// 
//
// 
// 查询 0 在 x = 7 处放置一个障碍物。在 x = 7 之前任何大小不超过 7 的物块都可以被放置。 
// 查询 2 在 x = 2 处放置一个障碍物。现在，在 x = 7 之前任何大小不超过 5 的物块可以被放置，x = 2 之前任何大小不超过 2 的物块可以
//被放置。 
// 
//
// 
//
// 提示： 
//
// 
// 1 <= queries.length <= 15 * 10⁴ 
// 2 <= queries[i].length <= 3 
// 1 <= queries[i][0] <= 2 
// 1 <= x, sz <= min(5 * 10⁴, 3 * queries.length) 
// 输入保证操作 1 中，x 处不会有障碍物。 
// 输入保证至少有一个操作类型 2 。 
// 
//
// Related Topics 树状数组 线段树 数组 二分查找 👍 9 👎 0


package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.TreeSet;

/**
 * 利用基础线段树
 */
class BlockPlacementQueries {
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<Boolean> getResults(int[][] queries) {
            List<Boolean> ans = new ArrayList<>();
            int maxV = Arrays.stream(queries).mapToInt(a -> a[1]).max().getAsInt();
            maxV++; //最大值+1为了添加哨兵
            SegmentTreeBase st = new SegmentTreeBase(maxV);
            TreeSet<Integer> xs = new TreeSet<>();
            xs.add(0);
            xs.add(maxV);
            for (int[] q : queries) {
                int x = q[1];
                int pre = xs.lower(x);
                if (q[0] == 1) {
                    int next = xs.higher(x);
                    st.update(x, x - pre);
                    st.update(next, next - x);
                    xs.add(x);
                } else {
                    int sz = Math.max(st.query(1, x), x - pre);
                    ans.add(sz >= q[2]);

                }
            }
            return ans;
        }
    }

    class SegmentTreeBase {
        private final int[] values;
        private final int maxV;

        public SegmentTreeBase(int maxV) {
            this.maxV = maxV;
            // 设置为4 * n也行, 下面写法更节省内存
            int sz = 2 << (32 - Integer.numberOfLeadingZeros(maxV));
            this.values = new int[sz];
        }

        /**
         * idx位置更新为val
         */
        public void update(int idx, int val) {
            this.update(1, 1, maxV, idx, val);
        }

        /**
         * 查询[l, r]区间和
         */
        public int query(int ql, int qr) {
            return this.query(1, 1, maxV, ql, qr);
        }


        /**
         * @param nodeId 当前节点id, 范围[l, r]
         * @param l      当前节点左边界
         * @param r      当前节点右边界
         * @param idx    修改的下标
         * @param val    新值
         */
        private void update(int nodeId, int l, int r, int idx, int val) {
            // 叶子节点
            if (l == r) {
                values[nodeId] = val;
                return;
            }
            int m = l + (r - l) / 2;
            if (idx <= m) {
                // 左子树
                update(nodeId * 2, l, m, idx, val);
            } else {
                //右子树
                update(nodeId * 2 + 1, m + 1, r, idx, val);
            }
            values[nodeId] = Math.max(values[nodeId * 2], values[nodeId * 2 + 1]);
        }


        /**
         * 查询区间[qL, qR] 的结果
         *
         * @param nodeId 当前节点id, 范围[l, r]
         * @param l      当前节点左边界
         * @param r      当前节点右边界
         * @param qL     查询区间左边界
         * @param qR     查询区间右边界
         */
        private int query(int nodeId, int l, int r, int qL, int qR) {
            // 如果节点区间位于查询区间之内，直接返回该区间的值
            if (qL <= l && qR >= r) {
                return values[nodeId];
            }
            int res = 0;
            int m = l + (r - l) / 2;
            if (qL <= m) {
                // 左子树包含部分查询区间
                res = Math.max(res, query(nodeId * 2, l, m, qL, qR));
            }
            if (qR > m) {
                // 左子树包含部分查询区间
                res = Math.max(res, query(nodeId * 2 + 1, m + 1, r, qL, qR));
            }
            return res;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}
